//给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 
//
// 
// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 
// 
//
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。 
//
// 
//
// 示例 1： 
//
// 
//输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
//输出：4
//解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
//其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 
//n 的值 3 。
// 
//
// 示例 2： 
//
// 
//输入：strs = ["10", "0", "1"], m = 1, n = 1
//输出：2
//解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= strs.length <= 600 
// 1 <= strs[i].length <= 100 
// strs[i] 仅由 '0' 和 '1' 组成 
// 1 <= m, n <= 100 
// 
//
// Related Topics 数组 字符串 动态规划 👍 1075 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

//java:一和零
public class Q0474OnesAndZeroes {
    public static void main(String[] args){
        Solution solution = new Q0474OnesAndZeroes().new Solution();
        solution.findMaxForm(new String[]{"10","0001","111001","1","0"}, 5, 3);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0) return 0;
        int len = strs.length;
        // dp[i][j][k] 表示在前 i个字符串中，使用 j 个 0 和 k个 1 的情况下最多可以得到的字符串数量。
//        int[][][] dp = new int[len + 1][m + 1][n + 1];
//        for (int i = 1; i < len + 1; i++) {
//            int countZero = countZeroInStr(strs[i - 1]);
//            int countOne = strs[i - 1].length() - countZero;
//            for (int j = 0; j < m + 1; j++) {
//                for (int k = 0; k < n + 1; k++) {
//                    if (j < countZero || k < countOne) dp[i][j][k] = dp[i - 1][j][k];
//                    // 如果当前字符串还能装进背包，那么前i-1个字符串所能满足的 j-zero 和 k-ones个数的0和1的子集个数，
//                        // 再加上当前字符串一个，就是最大满足0和1个数的子集。
//                    else dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - countZero][k - countOne] + 1);
//                }
//            }
//        }
        // 空间优化
        int[][] dp = new int[m + 1][ n + 1];
        for (int i = 1; i < len + 1; i++) {
            int countZero = countZeroInStr(strs[i - 1]);
            int countOne = strs[i - 1].length() - countZero;
            for (int j = m; j >= 0; j--) {
                for (int k = n; k >= 0; k--) {
                        // 如果当前字符串还能装进背包，那么前i-1个字符串所能满足的 j-zero 和 k-ones个数的0和1的子集个数，
                        // 再加上当前字符串一个，就是最大满足0和1个数的子集。
                    if (j >= countZero && k >= countOne) {
                        dp[j][k] = Math.max(dp[j][k], dp[j - countZero][k - countOne] + 1);
                    }
                }
            }
        }
        return dp[m][n];
    }

    public int countZeroInStr(String str) {
        if (str == null) return 0;
        int res = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') res++;
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}